package uestc.lj.basic.tree;

import java.util.HashMap;
import java.util.HashSet;

/**
 * 寻找一棵树上两个节点的最近公共祖先节点
 *
 * @Author:Crazlee
 * @Date:2021/11/23
 */
public class Code09_FindLowestCommonAncestor {
	public static class Node {
		public int value;
		public Node left;
		public Node right;

		public Node(int data) {
			this.value = data;
		}
	}

	public static Node findLowestCommonAncestor(Node head, Node node1, Node node2) {
		HashMap<Node, Node> fatherMap = new HashMap<>();
		fatherMap.put(head, head);
		process(head, fatherMap);
		HashSet<Node> set1 = new HashSet<>();
		Node cur = node1;
		while (cur != fatherMap.get(cur)) {
			set1.add(node1);
			cur = fatherMap.get(cur);
		}
		set1.add(head);
		cur = node2;
		while (!set1.contains(cur)) {
			cur = fatherMap.get(cur);
		}
		return cur;
	}

	private static void process(Node head, HashMap<Node, Node> fatherMap) {
		if (head == null) {
			return;
		}
		fatherMap.put(head.left, head);
		fatherMap.put(head.right, head);
		process(head.left, fatherMap);
		process(head.right, fatherMap);
	}

	public static Node findLowestCommonAncestor2(Node head, Node node1, Node node2) {
		if (head == null || head == node1 || head == node2) {
			return head;
		}
		Node left = findLowestCommonAncestor2(head.left, node1, node2);
		Node right = findLowestCommonAncestor2(head.right, node1, node2);
		if (left != null && right != null) {
			return head;
		}
		return left != null ? left : right;
	}
}
